package com.mystudy.leetcode.problem.link.p_141;

import com.mystudy.leetcode.base.ListNode;
import com.mystudy.leetcode.base.ListNodeUtils;
import org.junit.Test;

/**
 * @program: infoalgorithm
 * @description: 环形链表
 * @author: zhouzhilong
 * @create: 2019-07-05 10:52
 **/
public class Solution {


    @Test
    public void test(){
        ListNode listNode = ListNodeUtils.generateLinkList(new int[]{3, 2, 0, -4});
        ListNode cur = listNode;
        ListNode cyclePoint = null;
        while(cur != null){
            if(cur.val == 2){
                cyclePoint = cur;
            }
            if(cur.val == -4){
                cur.next = cyclePoint;
                break;
            }
            cur = cur.next;
        }
        boolean b = hasCycle(listNode);
        System.out.println(b);
    }

    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode lazy = head;
        boolean isCycle = false;
        while (fast != null && lazy != null) {
            if (fast.next == null || fast.next.next == null) {
                break;
            }
            fast = fast.next.next;
            if (fast == lazy) {
                isCycle = true;
                break;
            }

            if (lazy.next == null || lazy.next.next == null) {
                break;
            }
            lazy = lazy.next;
            if (lazy == fast) {
                isCycle = true;
            }

        }
        return isCycle;

    }
}
